# source:https://leetcode.cn/problems/palindrome-partitioning-ii/ 划分形DP
class Solution:
    def minCut(self, s: str) -> int:
        @cache
        def dfs(i):
            if i < 0:
                return -1
            res = inf
            for j in range(i+1):
                if judge[j][i]:
                    res = min(res, dfs(j-1)+1)
            return res
        n = len(s)
        judge = [[False]*n for _ in range(n)]
        for length in range(n):
            for i in range(n - length):
                j = i + length
                if s[i] == s[j] and abs(i-j) <= 1:
                    judge[i][j] = True
                elif s[i] == s[j]:
                    judge[i][j] = judge[i+1][j-1]
        return dfs(n-1)